'lintcode 同和分割数组'

Posted on | In

lintcode 同和分割数组

描述

给定一个有n个整数的数组，需要找到满足以下条件的三胞胎(i, j, k):
0 < i, i + 1 < j, j + 1 < k < n - 1
每个子数组的和(0,i - 1)， (i + 1, j - 1)， (j + 1, k - 1)和(k + 1, n - 1)应该相等。我们定义子数组(L, R)表示原始数组从元素索引L到元素索引R的一部分。

样例

给定 nums = [1,2,1,2,1,2,1], 返回 True

解释:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

思路

最简单的就是遍历完所有的ijk，但是复杂的是On^3，相当的高，可以使用j的遍历来代替k，即，j在寻找到一个区间与第一个区间相等后，继续往后搜索，如果再出现一个，就可以判断最后一个区间是否也符合。复杂度是On\^2.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    /**
     * @param nums: a list of integer
     * @return: return a boolean
     */


    bool splitArray(vector<int> &nums) {
        // write your code here
        vector<int> preSum;
        int res = 0;
        preSum.push_back(0);
        for (int i = 1; i <= nums.size(); i++) {
            res += nums[i-1];
            preSum.push_back(res);
        }

        for (int i = 1; i < nums.size(); i++) {
            int index = 0, j = i+1,
                sum = preSum[i],
                temp = 0;
            for (j = i+1; j < nums.size(); j++) {
                temp += nums[j];
                if (temp == sum) {
                    index++;
                    temp = 0;
                    j++;
                }
                if (index == 2)
                    break;
            }
            if (index == 2 && j != nums.size() &&sum == (preSum[preSum.size() - 1] - preSum[j+1]))
                return true;
        }
        return false;
    }
};
-------------end of filethanks for reading-------------